package com.example.Arithmetic.Arithmetic;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 日期：2023/12/29
 * 时间：20:21
 * 描述：迪克斯特拉算法，求最短路径
 * 1. 将所有顶点标记为未访问。创建一个未访问顶点的集合。
 * 2. 为每个顶点分配一个临时距离值
 * * 对于我们的初始顶点，将其设置为零
 * * 对于所有其他顶点，将其设置为无穷大。
 * 3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点
 * 4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
 * * 例如，1->6 的距离是 14，而1->3->6 的距离是11。这时将距离更新为 11
 * * 否则，将保留上次距离值
 * 5. 当前顶点的邻居处理完成后，把它从未访问集合中删除
 */
public class Dijkstra {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
        v2.edges = List.of(new Edge(v4, 15));
        v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
        v4.edges = List.of(new Edge(v5, 6));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5, 9));

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);

        dijkstra(graph, v1);
    }

    private static void dijkstra(List<Vertex> graph, Vertex vertex) {
//        顶点队列
        PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.dist));
//      当前顶点值设为0
        vertex.dist = 0;
        for (Vertex v : graph) {
            queue.offer(v);
        }

        while (!queue.isEmpty()) {
            System.out.println(queue);
//            选取当前顶点,寻找临时距离最小的作为当前顶点
            Vertex minDistVertex = queue.peek();
//            更新当前节点与邻居之间距离   邻居在集合中表示还没处理完
            if (!minDistVertex.visited) {
                updateNeighboursDist(minDistVertex, queue);
                minDistVertex.visited = true;
            }
//            移除当前顶点
            queue.poll();
        }
        for (Vertex vertex1 : graph) {
            System.out.println("名字:" + vertex1.name + "====" + "距离:" + vertex1.dist +
                    "====" +
                    "从哪里来：" + (vertex1.prev != null ? vertex1.prev.name : "null"));
        }
    }

    //                                                  当前顶点
    private static void updateNeighboursDist(Vertex minDistVertex, PriorityQueue<Vertex> queue) {
//           遍历顶点队列邻居
        for (Edge e : minDistVertex.edges) {
//            获得邻居武魂真身
            Vertex linked = e.linked;
//            看队列中是否包含邻居，如果有则更新
            if (!linked.visited) {
//                当前顶点距离加上邻居宽度=临时距离
                int i = minDistVertex.dist + e.weight;
//                临时小于邻居之前距离就更新邻居距离
                if (i < linked.dist) {
                    linked.dist = i;
                    linked.prev = minDistVertex;
                    queue.offer(minDistVertex);
                }
            }
        }
    }
}
